package leetcode.Hot100;

import java.util.Stack;

/**
 * @author Cheng Jun
 * Description: 请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。
 * 如果气温在这之后都不会升高，请在该位置用 0 来代替。
 * @version 1.0
 * @date 2021/11/13 22:20
 */
public class dailyTemperatures {

    public static void main(String[] args) {

    }

    // 遍历，嵌套循环 O(n^2)
    static int[] dailyTemperatures(int[] temperatures) {
        int[] days = new int[temperatures.length];
        // 循环 temperatures, 再循环 查找 i 后面第一个比 temperatures[i] 大的数字，找到 j - i, break, 找不到 0
        for (int i = 0; i < temperatures.length; i++) {
            inner:
            for (int j = i + 1; j < temperatures.length; j++) {
                if (temperatures[j] > temperatures[i]) {
                    days[i] = j - i;
                    break inner;
                }
            }
        }
        return days;
    }

    // 单调栈（栈元素具有单调递增或单调递减性质的栈），时间复杂度为 O(n)
    // 维护一个 单调栈，栈元素是数组下标，比较的元素是 temperatures[i]
    // 入栈逻辑：栈为空或 temperatures[i] 小于等于 栈顶元素
    // 出栈逻辑：temperatures[i] 大于栈顶元素，出栈，并计算对应下标差（天数）,然后 i--，使得这个元素再次和新的栈顶元素比较
    // 10 9 8 11 12
    static int[] dailyTemperatures1(int[] temperatures) {
        Stack<Integer> indexStack = new Stack<>();
        int[] days = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            if (indexStack.isEmpty()) {
                indexStack.push(i);
            } else {
                int index = indexStack.peek();
                if (temperatures[i] <= temperatures[index]) {
                    indexStack.push(i);
                } else {
                    indexStack.pop();
                    days[index] = i - index;
                    // 注意 这里 i-- 表示这天温度还没有入栈。
                    i--;
                }
            }
        }
        return days;
    }
}
